The present invention relates generally to high-speed adders, and more particularly to a method and apparatus for performing arithmetic using a high-speed radix 100 parallel adder.
Input to conventional binary parallel adders are decimal digits represented in binary coded decimal (BCD) format. As shown in FIG. 1A, BCD uses a combination of four binary bits, b3, b2, b1, and b0, to represent the decimal digits 0 through 9. In the binary number system, each bi coefficient has a value of 0 or 1, and the subscript value i indicates the power of 2 by which the coefficient must be multiplied:
b3*23+b2*22+b1*21+b0*20
The decimal number a system, in contrast, is said to be of base, or radix, 10 because it uses 10 digits and each coefficient is multiplied by powers of 10. Each digit of a decimal number input into a computer is converted into the corresponding BCD code before arithmetic operations are performed on the number.
FIG. 1B is a diagram showing an example addition of two BCD operands by a conventional binary parallel adder. The operand A is the representation of the decimal number 752 and operand B is the representation of the decimal number 836. Each digit in the operands is represented by a corresponding 4-bit BCD digit. The adder adds the corresponding BCD digits from the operands, which produces digit sums and digit carries for each coefficient, where the digit carries are added to the next set of digits.
Referring again to FIG. 1A, the four BCD variables have a total of sixteen distinct codes or values, only ten of which are used for representing decimal digits. The remaining six values are not used or are invalid. The addition of two BCD digits has the potential to produce a value that is invalid. That is, any digit sum greater than 1001 is invalid and must be corrected during the addition.
Referring back to FIG. 1B, a binary parallel adder ensures that every digit sum results in a valid value by adding binary six (0110) to each digit addition, which is referred to as xe2x80x9cforcing sixes.xe2x80x9d Each digit sum is then examined for digit carries. If a digit sum did produce a digit carry, then adding the binary six was necessary to produce a valid digit sum. If a digit sum did not produce a digit carry (NC), then the addition of the binary six was unnecessary, so the binary six is subtracted from the digit sum. This is done by adding the 1""s complement of binary six (1001) and a hot 1 for the 2""s complement. The result is a final sum that also may or may not include a final carry. In this example, the final sum includes a final carry and represents the decimal number 1588.
As the example shows, the adder performs three additions per digit to produce the final sum. Of course, conventional adders are sophisticated enough to perform all these operations in parallel to speed computations. Although the design of a conventional parallel binary adder is adequate, the method of representing radix 10 numbers in BCD has disadvantages.
One disadvantage with performing arithmetic on radix 10 numbers in BCD is that the BCD code is inefficient because six of the ten combinations are not used. In addition, in order to allow byte operations, each 4-bit BCD digit is padded with 4-bits (typically 111) to make an eight bit value. Thus, one byte, or eight bits, is used to represent only nine values, which is inefficient from a coding point of view.
Another disadvantage with performing binary arithmetic by a binary parallel adder on radix 10 numbers is that when interacting with computers, humans prefer to input numbers and view results in decimal form (radix 10). However, in the binary system, certain arithmetic operations do not produce results that humans expect. For example, humans would expect the result of 1 divided by 5 to be 0.2. But after this arithmetic is performed in a binary number system by a conventional adder, the result is often 0.19999.
Accordingly, what is needed is an improved method and apparatus for performing decimal arithmetic. In addition, the method and apparatus should perform on pair with conventional high-speed binary adders. The present invention addresses such a need.
The present invention provides a method and apparatus for performing radix 100 decimal arithmetic. A radix 100 parallel adder is disclosed comprising several levels of logic for adding at least two operands, each having at least one seven-bit radix 100 digit. A first logic level receives the at least two operands and generates outputs comprising a bit carry propagate value, a bit carry generate value, and half sum value for each bit position. A second logic level receives the output from the first logic level and generates outputs comprising group carry propagate values and group carry generate values. A third logic level receives the output from the second logic level and generates outputs comprising a digit carry-out value. A fourth logic level receives the outputs from first logic level and generates outputs comprising bit carry values. A fifth logic level receives the output from the second logic level and generates outputs comprising a digit group carry generate and a digit group carry propagate for the at least one radix 100 digit. And a sixth logic level receives the output is from the first logic level and the outputs from the fourth logic level and generates a final sum for the at least one radix 100 digit.
According to the apparatus and method disclosed herein, the several levels of logic of the radix 100 parallel operate in parallel to provide the final sum within one clock cycle and should be as fast as today""s state-of-the-art high-speed parallel binary adders.